{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "访问树节点node和拉格朗日插值测试，本次测试为了直观，不使用$ GF\\left( p \\right)  $上的大整数元素，并且使用了numpy和scipy已有的相关实现。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from scipy.interpolate import lagrange # 拉格朗日插值函数\n",
    "from node import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 拉格朗日插值多项式\n",
    "对某个多项式函数，已知有给定的$k+1$个取值点：$ \\left( x_0,y_0 \\right) ,\\left( x_1,y_1 \\right) ,...,\\left( x_k,y_k \\right)  $，其中$x_j$对应着自变量的位置，而$ y_j $对应着函数在这个位置的取值。假设任意两个不同的$x_j$都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：\n",
    "$$\n",
    "f\\left( x \\right) =\\sum_{j=0}^k{y_jl_j(x)}\n",
    "$$\n",
    "其中的$l_j(x)$称为拉格朗日插值基函数，其表达式为：\n",
    "$$\n",
    "l_j(x)=\\prod_{i=0,i\\ne j}^k{\\frac{x-x_i}{x_j-x_i}}=\\frac{\\left( x-x_0 \\right)}{\\left( x_j-x_0 \\right)}\\cdots \\frac{\\left( x-x_{j-1} \\right)}{\\left( x_j-x_{j-1} \\right)}\\frac{\\left( x-x_{j+1} \\right)}{\\left( x_j-x_{j+1} \\right)}\\cdots \\frac{\\left( x-x_k \\right)}{\\left( x_j-x_k \\right)}\n",
    "$$\n",
    "例如：我们考虑任意的三个点：$ \\left( x_0,y_0 \\right) =\\left( 1,6 \\right) , \\left( x_1,y_1 \\right) =\\left( 2,11 \\right) , \\left( x_2,y_2 \\right) =\\left( 3,18 \\right)  $ 带入$l_j(x)$计算得到\n",
    "$$\n",
    "l_0=\\frac{x-2}{1-2}\\frac{x-3}{1-3}=\\frac{1}{2}x^2-\\frac{5}{2}x+3\n",
    "\\\\\n",
    "l_1=\\frac{x-1}{2-1}\\frac{x-3}{2-3}=-x^2+4x-3\n",
    "\\\\\n",
    "l_2=\\frac{x-2}{5-2}\\frac{x-4}{5-4}=\\frac{1}{2}x^2-\\frac{3}{2}x+1\n",
    "$$\n",
    "最后带入$f(x)$得到插值多项式：\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\tf\\left( x \\right) &=\\sum_{j=0}^2{y_jl_j(x)}\\\\\n",
    "\t&=6\\left( \\frac{1}{2}x^2-\\frac{5}{2}x+3 \\right) +11\\left( -x^2+4x-3 \\right) +18\\left( \\frac{1}{2}x^2-\\frac{3}{2}x+1 \\right)\\\\\n",
    "\t&=3+2x+x^2\\\\\n",
    "\\end{aligned}\n",
    "$$\n",
    "下面的代码验证了这一事实"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------\n",
      "   2\n",
      "1 x + 2 x + 3\n",
      "---------------\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAEICAYAAABGaK+TAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8qNh9FAAAACXBIWXMAAAsTAAALEwEAmpwYAAA0aUlEQVR4nO3deVyVZfrH8c8FsqmIGy6AioqYW264pZa2Wdqi9aupLMslp5qydZqmnMpWZ6ZsWmw1l9LMrLHUUcvSUstSXFFBEVxAFkFFVHbO/fvjPBoSyAEOHA5c79eLF+dZ7+s5wJfn3M8mxhiUUkq5Hw9XF6CUUqpiNMCVUspNaYArpZSb0gBXSik3pQGulFJuSgNcKaXclAa4g0Sks4hsF5FTIjLFGjdCRL52cPlNItKtSousAURkt4gMc3UdriQi94jIhkosv1JE7nZmTZUhInNF5CVX11GUiDwtIrMcnLfG1e8sGuCOexJYa4zxN8a8ZY17GZju4PKvAS+UNrGyf/Q1hTGmmzHmR2evV0SeF5H5Ds7rNu9lSdtljLnWGDOvCtqaKyJ5InJaRI6LyGoRucjZ7VQHY8wrxphJrq7D1TTAHdcO2H12QET6AQHGmF8dXH4pMFxEWlVFcY4SEU9Xtu8ORKSeq2uoQv8yxjQEQoCjwFzXlqMqQwPcASKyBhgOvGPtvYQD1wI/FZnnEhFJF5E21nBPETlxdg/HGJMDbAFGVKD98SISbXXfxIvIn4tNf1JEkkUkSUQmiYgRkTBr2lwReU9EVojIGez/REaJyDYRyRSRBBF5vsi6Qq3l7xaRw9Y2PVNkup+IzLO2LdpqO7HI9IMicqX1ur+IbBSRDKu+d0TEu8i8RkTuE5FYa56ZIiIOviclLisiXYD3gUHWzyrDmt9HRF6ztilVRN4XET9r2jARSRSRv4lICjCnyLinrffgoIiMLdJ+gIh8IiJpInJIRKaKSIl/TyLypvU+Z4rIFhEZao2/Bnga+JNV6w5r/I8iMsl67WGt+5CIHLXaDHDkZ3Uhxpgs4DOgu7WuLla7GWLvBruhlG3ZJSLXFxn2strt7cDvjo+I/Mf6PU2yXvsU+xk8aW1nsoiMFpGRIrJP7J8Yni6yrvM+uYjIYhFJEZGTIrJO6kB3JWiAO8QYczmwHnjQGNPQGLMP6AHsLTLPL8AHwDwrGOYD/zDGxBRZVTTQswIlHAWuAxoB44E3RKQPnAuBx4ArgTBgWAnL34G9u8cf2ACcAcYBjYFRwP0iMrrYMkOAzsAVwLNWMAI8B4QCHYCrgDsvUHch8CjQHBhkreuBYvNcB/QDLgZupXz/4P6wrDEmGrgP2Gj9rBpb804HwoFe2N+nYODZIutqBTTF/klrcpFxza157wY+FJHO1rS3gQDs78Nl2N/P8aXUudlqtyn20FwsIr7GmFXAK8Aiq9aSfjfusb6GW201BN4pNk9pP6tSiUhDYCywTUS8gGXAd0AL4CFgQZFtLeoTzv+ZjwSSjTHbHKjnGWAg9veiJ9AfmFpkuVaAL7//bD6y2uoLDAX+ISLtS9mklUAnq/6twIILvwO1hDFGvxz4An4EJhUZXg3cV2weL+x72VHAKkCKTX8ZmF3K+u8BNjhYy9fAw9br2cCrRaaFAQYIs4bnAp+Usb7/AG9Yr0Ot5UOKTN8E3Ga9jscelGenTQISiwwfBK4spZ1HgCVFhg0wpMjwF8BTpSz7PDDfkWWLv5eAYP+n1bHIuEHAAev1MCAP8C0yfRhQADQo1sY/AE9r/q5Fpv0Z+NGRnyVwAuhZ0nYV/10DfgAeKDKtM5AP1CvrZ1VCu3OBHCADSMHerdcRezimAB5F5l0IPF9kuZes10HAKaCRNfwl8KSDvztxwMgi00YAB4u839mApzXsb61rQJH5twCjS3vfiszX2Fo2oHj9te1L98Ar7gT2X7JzjDH52H9ZugOvG+u3pwh/7H885SIi14rIr9bHyAzsez3NrclBQEKR2ROKL198nIgMEJG11sf/k9j3WJsXWyalyOss7Ht+jrZ3tp1wEVlufbTNxL636Wg7jnB02UCgPrDF6iLIwP4PNrDIPGnG3s1V1AljzJkiw4ewb39z7P+sDxWbFlxS4yLyhNi7m05abQfwx/ehNEEltFMPaFlkXHnew9eMMY2NMa2MMTcYY+KsNhKMMbaytscYkwT8DNwsIo2xdyUW39u90O9O8W0JKjJ8zBhTaL3Otr6nFpmeXdK2iYiniEwXkTjr9+ygNcnR99htaYBX3E7sH8nPEZFg7F0Mc4DXz/bvFdEF2FGeRqx1fIX9LJaWxt4lsAL7XiVAMvYDUme1KWE1xf+RfIZ976uNMSYAe5+xQ33PDrZ31ntADNDJGNMIe3+vo+1URvHtTcf+x9/NCq/GxpgAYz+YV9oyAE1EpEGR4bZAkrW+fOzdLUWnHSm+Aqu/+0nsXTxNrJ/fSX5/H8q6HWhSCe0UcH6wVVYS0KZYH36J22OZh71r4xbsXVWlzVdSO8W3JamctZbkDuBG7N2IAdg/CUD1/K65lAZ4xa3A3vcJgIgI9r3vj4GJ2IPuxSLTfbH35a2+wDpFRHyLfgHegA+QBhSIyLXA1UWW+QIYbx2Eqo/9I35Z/IHjxpgcEemP/Q/AUV8AfxeRJtY/rAfLaCcTOC32g7n3l6OdykgFQsQ6YGrtWX6E/dhBC7D/sxURR/rbp4mItxXE1wGLrb3EL4CXRcRfRNphPw5R0mmO/tgDNw2oJyLPYj+WUbTWUCnlACj2roxHRaS91W99ts+8wIHaHfUb9j3lJ62DksOA64HPS5n/a6AP8DD2PnFHLQSmikigiDTH3s/t0KmhZfAHcoFj2D9pveKEdboFDfAKMsZsBU6KyABr1BTsB1D+YXWdjMcerEOt6ddj7yO90B7HJdj3FIt/TcEeGCewh+3SInWsBN4C1gL7gbOnNeZeoJ0HgBdE5BT2P6IvHNlmywtAInAA+B57H2hpbT1h1XsKe4AuKkc7lbEG+ymfKSKSbo37G9b7Y33M/h57f/KFpGB/z5OwdxPcZ34/KP0Q9n71eOwHhj/DfjyiuG+xd9fsw95lkMP53U6Lre/HRGRrCcvPBj4F1mF/z3Ostp3GGJOH/ffzWuyfLt4FxpnzD8AXnT8b+6fC9sB/y9HUS0Ak9k+vUdgPNjrjAptPsL+3R4A9/P43UOvJH7tplaNE5GrsB5hGOzDvb8BEY8yuKq6pC7AL8HHyXlpp7d2P/SDVZWXO7EasvdD5xpiQMmatk6xPEuHGmAudhaSqmO6BV4Ix5jtHwtuad0BVhbeIjLHOsW0C/BNYVlXhLSKtRWSw2M9P7gw8DiypirZUzSQiTbF3E37o6lrqOg3w2uHP2M8Vj8N+7nVV9jV7Yz/f/RT2ropvsH/kVnWAiNyLvQtopTFmnavrqeu0C0UppdyU7oErpZSbqtab9jRv3tyEhoZWZ5NKKeX2tmzZkm6MCSw+vloDPDQ0lMjIyOpsUiml3J6IHCppvHahKKWUm9IAV0opN6UBrpRSbkoDXCml3JQGuFJKuSkNcKWUclMa4Eop5aY0wJVSqgrl5BcybdluEo5nOX3dGuBKKVWFFm46zJyfD5KUkV32zOWkAa6UUlUkJ7+Q93+KY0D7pgzo0Mzp69cAV0qpKrJ4SyKpmblMuaJTlaxfA1wppapAXoGN93+Mo0/bxlzS0fl736ABrpRSVWLJtkSOZGTz0BWdsD/z3Pk0wJVSyskKCm3MXBvHxSEBDAv/w11gnUYDXCmlnOyb7UkcPp7FQ5dX3d43aIArpZRTFdoMM9fup0vrRlzZpUWVtqUBrpRSTvS/qGTi08/w0OVhVbr3DRrgSinlNDab4Z01sXRq0ZBrurWq8vY0wJVSykm+3Z3CvtTTPHh5GB4eVbv3DRrgSinlFMYY3l6znw7NG3DdxUHV0qYGuFJKOcEP0UfZk5zJA8PD8KyGvW9wIMBFpI2IrBWRPSKyW0QetsY/LyJHRGS79TWy6stVSqmaxxjDG9/vo23T+tzYq3r2vgHqOTBPAfC4MWariPgDW0RktTXtDWPMa1VXnlJK1Xzf7Ulld1Imr93SEy/P6uvYKDPAjTHJQLL1+pSIRAPBVV2YUkq5A5vN8J/vY2nfvAGjq3HvG8rZBy4ioUBv4Ddr1IMislNEZotIk1KWmSwikSISmZaWVrlqlVKqhvl2dwrRyZk8dHkY9apx7xvKEeAi0hD4CnjEGJMJvAd0BHph30N/vaTljDEfGmMijDERgYFVd08ApZSqbmf3vjsENuCGntW79w0OBriIeGEP7wXGmP8CGGNSjTGFxhgb8BHQv+rKVEqpmmfFrmT2pp7i4Ss6VfveNzh2FooAHwPRxpgZRca3LjLbGGCX88tTSqmaqdBmePP7WMJaNKy2876Lc+QslMHAXUCUiGy3xj0N3C4ivQADHAT+XAX1KaVUjbR8ZxKxR0/z9u29q+287+IcOQtlA1BSdSucX45SStV8hTbDmz/EEt6yIaN6tC57gSqiV2IqpVQ5Ld1xhPi0MzxyZXi13POkNBrgSilVDgWFNt76YT8XtfKvljsOXogGuFJKlcPX25M4kO76vW/QAFdKKYflFdh484d9dAtqxIhuLV1djga4Uko5alFkAgnHs3liROcqf9qOIzTAlVLKAdl5hbz9Qyz9QptU6ZPmy0MDXCmlHPDJxoMcPZXLX0dcVCP2vkEDXCmlypSZk897P8VxWXgg/ds3dXU552iAK6VUGWatP0BGVj5PXN3Z1aWcRwNcKaUu4NjpXD5eH8/IHq3oERLg6nLOowGulFIX8O6PcWTnF/LYVTVr7xs0wJVSqlRJGdl8+ushbu4TQliLhq4u5w80wJVSqhRvr4nFGMPDV3ZydSkl0gBXSqkSHEg/wxeRiYwd0I6QJvVdXU6JNMCVUqoEM1bvw9vTgweGd3R1KaXSAFdKqWJ2HTnJsh1JjB8cSgt/X1eXUyoNcKWUKmb6yhia1PfivmE1d+8bNMCVUuo86/alsWF/Og9e3olGvl6uLueCNMCVUspisxmmr4whpIkfdw5s6+pyyqQBrpRSlm92HGFPciZ/HdEZn3qeri6nTBrgSikF5OQX8tq3++ge3IjrLw5ydTkO0QBXSilg/q+HOJKRzVPXdHH5o9IcpQGulKrzTmbn887a/Qzt1JwhnZq7uhyHaYArpeq8936M42R2Pk9de5GrSykXDXClVJ2WlJHNnJ8PMLpXMN2CatbtYsuiAa6UqtPeWL0PY+Cxq8JdXUq5aYArpeqs6ORMvtqayLhB7WjTtGbesOpCNMCVUnWSMYaX/reHRn5ePHR5zbxdbFk0wJVSddKamKP8vP8YD1/RiYD6NfuS+dJogCul6pz8Qhsvr4imQ/MG3DmwnavLqbAyA1xE2ojIWhHZIyK7ReRha3xTEVktIrHW9yZVX65SSlXegl8PEZ92hqdHdsHL0333Yx2pvAB43BjTFRgI/EVEugJPAT8YYzoBP1jDSilVo53Myuc/P8QyOKwZV3Rp4epyKqXMADfGJBtjtlqvTwHRQDBwIzDPmm0eMLqKalRKKad5e00sJ7PzeWZkV0Tc45L50pTrs4OIhAK9gd+AlsaYZGtSCtDSuaUppZRzHUg/w7yNB/lTRBu6BjVydTmV5nCAi0hD4CvgEWNMZtFpxhgDmFKWmywikSISmZaWVqlilVKqMqavjMbL04PHrna/i3ZK4lCAi4gX9vBeYIz5rzU6VURaW9NbA0dLWtYY86ExJsIYExEYGOiMmpVSqtw2xh3j292pPDCsY41+zmV5OHIWigAfA9HGmBlFJi0F7rZe3w184/zylFKq8mw2+0U7QQG+TBrawdXlOE09B+YZDNwFRInIdmvc08B04AsRmQgcAm6tkgqVUqqSvtyayO6kTN68rRe+XjX/STuOKjPAjTEbgNIO1V7h3HKUUsq5MnPy+deqGPq0bcwNPd3jSTuOcmQPXCml3NZb38dy7Ewec+7p7/anDRbnvpcgKaVUGfYfPcXcXw5yW7829Ahxr3t9O0IDXClVKxljmLZsD/W9PXni6s6uLqdKaIArpWqV7OxsLrvsMlZFJbE+Np3HrgqnWUOf8+ZZvXo1ffv2pUePHvTt25c1a9ZUuL2xY8fSuXNnunfvzoQJE8jPzwdg+fLlPPvss5XalrJogCulapXZs2dz/Y2jeWXVXsJbNizxboPNmzdn2bJlREVFMW/ePO66664Ktzd27FhiYmKIiooiOzubWbNmATBq1CiWLVtGVlZWhdddFg1wpVStsmDBAk637EXC8WyG+xxkxNVXYYwhOTmZ8PBwUlJS6N27N0FB9jNSunXrRnZ2Nrm5uaWuMy4ujj59+pwbjo2NPTc8cuRIRAQRoX///iQmJgIgIgwbNozly5dX2bZqgCulao28vDz2x8XxeUwOI3u04u8P3E3r1q2ZOXMm9957L9OmTaNVq1bnLfPVV1/Rp08ffHx8SlkrdOzYkYCAALZv3w7AnDlzGD9+/Hnz5Ofn8+mnn3LNNdecGxcREcH69eudt4HFaIArpdxe6oJUNoZuZKnPUnyO+RAR5cnTI7sA8Pbbb/Pqq6/i4+PD7bffft5yu3fv5m9/+xsffPBBmW1MmjSJOXPmUFhYyKJFi7jjjjvOm/7AAw9w6aWXMnTo0HPjWrRoQVJSkhO2sGQa4Eopt5a6IJW9k/eSeygXH3zIL8xjwiofvFacAiAxMREPDw9SU1Ox2WznlktMTGTMmDF88skndOzYscx2br75ZlauXMny5cvp27cvzZo1Ozdt2rRppKWlMWPGjPOWycnJwc/Pz0lb+kca4Eoptxb/TDy2LHsw++OPDRsFubnEPxNPQUEBEyZMYOHChXTp0uVcwGZkZDBq1CimT5/O4MGDz1vfuHHj2LRp0x/a8fX1ZcSIEdx///3ndZ/MmjWLb7/9loULF+LhcX6k7tu3j+7duzt7k8/RAFdKubXcw+cffIwggiiiyD2cyyuvvMLQoUMZMmQIM2bMYNasWURHR/POO++wf/9+XnjhBXr16kWvXr04etR+Q9WdO3eeO8BZ3NixY/Hw8ODqq68+N+6+++4jNTWVQYMG0atXL1544YVz09auXcuoUaOqYKvt9FJ6pZRb82nrQ+6h30N8NKP5ki+5pO0l552H7e/vT0xMDABTp05l6tSpf1hXZmYmnTp1IiQkpMS2NmzYwPjx4/H0/P2GWAUFBSXOm5qaSnZ2Nj169KjQdjlCA1wp5dY6vNyBqAnR1MuzD4cTTm/v3rR7sfxPm2/UqBGLFy8ucdqYMWOIi4tz+KKfw4cP8/rrr5e7hvIQ+8N0qkdERISJjIystvaUUrXfmphUPvzrNiZsboD30UJ82vrQ4eUOtBxbe57yKCJbjDERxcfrHrhSym1l5xXy7De78R3ux7Alg/GuV7cO62mAK6Xc1sy1+0k8kc3CewfWufAGPQtFKeWm4tJO88G6OMb0DmZQx2ZlL1ALaYArpdyOMYZ/fL0LX6/fr7isizTAlVJuZ+mOJH6JO8aTIzoT6F/6PUxqOw1wpZRbycjK48Xle7g4JIA7BpT/VMHaRA9iKqXcyisrojmRlc+8Cf3x9Khdz7gsL90DV0q5jV/i0vkiMpFJQ9vTLaj2PeOyvDTAlVJuISe/kKf/G0XbpvV55IpwV5dTI2gXilLKLbz1QywHj2Uxf+IA/Lw9y16gDtA9cKVUjRednMmH6+K5uU8IQzo1d3U5NYYGuFKqRiu0GZ76aicBfl5MHVV3z/kuiQa4UqpGm/fLQXYknuTZ67vSpIG3q8upUTTAlVI1VuKJLF77bi/DOgdyQ8+SH7JQl2mAK6VqpLOXywO8NLo7InX7nO+SaIArpWqkr7YeYe3eNJ64ujMhTeq7upwaSQNcKVXjpJzMYdqy3fQLbcI9l4S6upwaq8wAF5HZInJURHYVGfe8iBwRke3W18iqLVMpVVcYY3h6SRT5hTb+9X898ajjl8tfiCN74HOBa0oY/4Yxppf1tcK5ZSml6qr/bj3Cmpij/HXERbRv3sDV5dRoZQa4MWYdcLwaalFK1XGpmfauk4h22nXiiMr0gT8oIjutLpYmpc0kIpNFJFJEItPS0irRnFKqNjPG8PR/o8gtsPHvW3rW+TsNOqKiAf4e0BHoBSQDr5c2ozHmQ2NMhDEmIjAwsILNKaVquyXbjvBDzFH+OqKzdp04qEIBboxJNcYUGmNswEdAf+eWpZSqS1Izc3h+qb3rZPzg9q4ux21UKMBFpHWRwTHArtLmVUqpCzHG8MwSe9fJv/7vYu06KYcybycrIguBYUBzEUkEngOGiUgvwAAHgT9XXYlKqdps8ZZEvo8+ytRRXegQ2NDV5biVMgPcGHN7CaM/roJalFJ1zOFjWUxbupsB7Ztq10kF6JWYSimXKLQZHvtiOx4ivH6rnnVSEfpEHqWUS7z/UxyRh07wxp966r1OKkj3wJVS1W7XkZO8sXofo3q0ZnSvYFeX47Y0wJVS1Sonv5BHFm2nWUNvXh6jt4mtDO1CUUpVq+krY9h/9DSfTuxP4/r6hJ3K0D1wpVS1WR+bxtxfDnLPJaEM7aRXZleWBrhSqlpkZOXxxOIdhLVoyFPXXuTqcmoFDXClVJUzxvDklzs5fiaP//ypF75enq4uqVbQAFdKVbn5vx7iuz2pPDniIroHB7i6nFpDA1wpVaWikzN58X/RXBYeyMQherWlM2mAK6WqTFZeAQ9+tpUAPy9ev1Ufj+ZsehqhUqrKTFu6h/j0M8yfOIDmDX1cXU6to3vgSqkqsXRHEosiE3hgWEcGhzV3dTm1kga4UsrpDh/L4un/RtGnbWMeuTLc1eXUWhrgSimnyiuw8dDn2/AQePO23nh5asxUFe0DV0o51b+/jWFHQgbvje1Dm6Z6l8GqpP8alVJOs2pXMh+tP8BdA9txbY/WZS+gKkUDXCnlFAfSz/DXxTvp2aYxU6/r4upy6gQNcKVUpWXnFXL//C3U8xTeHdsHn3p6qXx10ABXSlVIdnY2l112GQUFBUz9ehd7U0/xn9t6E9zY79w8x44dY/jw4TRs2JAHH3ywUu298847hIWFISKkp6efG798+XKeffbZSq3bXWmAK6UqZPbs2dx0000s3prEV1sTmXJ5Jy4LP/8Wsb6+vrz44ou89tprlW5v8ODBfP/997Rr1+688aNGjWLZsmVkZWVVug13owGulKqQBQsW0Ln/cJ5bupt2p3axbPr9GGNITk4mPDyclJQUGjRowJAhQ/D19XVonXFxcfTp0+fccGxs7Lnh3r17Exoa+odlRIRhw4axfPlyp2yXO9EAV0qVW15eHnFx8by0Lp3mDbxZ8q9HCWrdmpkzZ3Lvvfcybdo0WrVqVe71duzYkYCAALZv3w7AnDlzGD9+fJnLRUREsH79+nK35+40wJVSDktdkMrG0I0s9VmKV7o37X7JZ+bYPjRt4M3bb7/Nq6++io+PD7fffnuF25g0aRJz5syhsLCQRYsWcccdd5S5TIsWLUhKSqpwm+7KLQLcGMOx07muLkOpOi11QSp7J+8l91AuPvhQYMtj4ne+BK3PAyAxMREPDw9SU1Ox2WwVbufmm29m5cqVLF++nL59+9KsWbMyl8nJycHPz6/M+Wobtwjwacv28H/vb+RkVr6rS1Gqzop/Jh5blj2Y/fHHho2CnFzin4mnoKCACRMmsHDhQrp06cKMGTPKXN+4cePYtGnTH8b7+voyYsQI7r//foe6TwD27dtH9+7dy7dBtYBbBPh1F7cm8UQWDy7cSkFhxf+zK6UqLvfw+Z+CI4ggiihyD+fyyiuvMHToUIYMGcKMGTOYNWsW0dHRAISGhvLYY48xd+5cQkJC2LNnDwA7d+4kKCioxLbGjh2Lh4cHV1999blxb731FiEhISQmJnLxxRczadKkc9PWrl3LqFGjnL3JNZ5b3AslIrQpL4/uwZNf7eTlFdE8d303V5ekVJ3jFeJNfkLeueHRjOZLvuSStpecdx62v78/MTEx54YPHjz4h3VlZmbSqVMnQkJCSmxrw4YNjB8/Hk/P3y8ImjJlClOmTPnDvKmpqWRnZ9OjR4+KbJZbc4sAB7i1XxtiUk4x++cDXNTKnz/1a+vqkpSqM/IKbPzvykIu+9TgU2B/qk444fT27k27F9uVsfQfNWrUiMWLF5c4bcyYMcTFxbFmzRqH1nX48GFef/31ctdQG4gxptoai4iIMJGRkRVevqDQxoR5kWyMS+ezewfSL7SpE6tTSpXmmSVRLPjtMO826kCTDzPIPZyLT1sfOrzcgZZjW7q6vFpPRLYYYyL+MN6dAhzgZHY+Y2b+zMnsfL55cDAhTfR2lUpVpQW/HeKZJbu477KOPHXtRa4up04qLcDLPIgpIrNF5KiI7CoyrqmIrBaRWOt7E2cXXJoAPy8+ujuCvEIbk+ZFcia3oLqaVqrO+Xl/Os99s5thnQP564jOri5HFePIWShzgWuKjXsK+MEY0wn4wRquNh0DGzLzjj7sSz3Fo4u2Y7NV36cIpeqK2NRT3Dd/Cx0DG/LW7b3x1CfK1zhlBrgxZh1wvNjoG4F51ut5wGjnllW2S8MDmTqqK9/tSWX6qpiyF1BKOSztVC73zNmMr5cns8f3o5Gvl6tLUiWo6FkoLY0xydbrFKDUoxgiMhmYDNC2rXPPHBk/OJSDx87w4bp4Qpr4MW5QqFPXr1RdlJ1XyKRPIjl2Jpcv/jzovNvDqpql0hfyGPtR0FL7MIwxHxpjIowxEYGBgaXNViEiwnPXd+PKLi14fuluvt+T6tT1K1XX2GyGRxdtZ2diBm/e1puLQxq7uiR1ARUN8FQRaQ1gfT/qvJLKx9NDeOv23nQPDuChhdvYkZDhqlKUcnvTV8WwancKz4zswohu5b+boKpeFQ3wpcDd1uu7gW+cU07F1Peux8d396NZQ28mzttMwvG6d2N3pSpr/q+H+HBdPOMGtWPikPauLkc5wJHTCBcCG4HOIpIoIhOB6cBVIhILXGkNu1Sgvw9zx/cnv9Bwz5xNZGTllb2QUgqA7/ek8tzS3QzvHMiz13VFRM84cQeOnIVyuzGmtTHGyxgTYoz52BhzzBhzhTGmkzHmSmNM8bNUXCKsRUM+vKsvCcezmfzpFnILCl1dklI13uaDx/nLZ1vpFtSIt+/oQz1Pt7jHncJN7kZYHgM6NOO1W3uy6cBxHl64Xe9eqNQFxKRkMnHuZoIb+zHnnn409HGb2yMpamGAA9zQM4hnr+tqPxizZBfVebsApdxFwvEsxn28CT9vTz6Z2J9mDX1cXZIqp1r773bCkPZkZOXx1pr9BNT34u/XXqT9ekpZ0k/nMm72JnLyC1l83yV6TyE3VWsDHODRq8LJyM7nw3XxNK7vxQPDwlxdklIudyonn3vmbCL5ZDbzJw6gcyt/V5ekKqhWB7iI8Pz13TiZnc+/Vu2lsZ83dwzQ+4iruiu3oJA/f7qF6ORTfDSuLxF6S2a3VqsDHMDDQ3jtlp6cyingma+j8Petx/U9S36Mk1K1WV6Bjb8s2MYvccd4/ZaeXH6R3sfb3dXKg5jFeXl6MPOOPkS0a8JjX2xn7V6XXTiqlEsUFNp4+PNtfB+dygs3duPmviU/yky5lzoR4AB+3p7Mursf4S39+fOnW1i3L83VJSlVLQpthse+2MHKXSlMHdVFb/pWi9SZAAf7wyDmTxxAx8CG3PtJJBti011dklJVymYz/O2rnSzdkcTfrrmISUM7uLok5UR1KsABmjTwZsGkAbRv3oCJ8zbzy34NcVU7GWN45utdfLklkUevDOf+YR1dXZJysjoX4ABNrRAPbdaACfM2szHumKtLUsqpjDE8v3Q3Czcd5sHhYUy5Qk+hrY3qZIADNGvow4J7B9CmSX0mzN3Mr/Ea4qp2MMbwwvI9zNt4iMmXduDxq8P1IrZaqs4GOEDzhj58du9Agpv4MX7OZn7TEFduzmYzPL1kF3N+PsjEIe31CuRark4HONhvQ/vZvQMIauzLPXM269kpym0VFNp4fPGOc90mU0d10fCu5ep8gAO08Pfl88mDCG3egEnzIlm1K7nshZSqQfIKbDy0cBtLth3hryM688SIzhredYAGuCXQ34fP7x1I9+BGPLBgK19uSXR1SUo5JCe/kD9/GsnKXSn847qu/GW4HrCsKzTAiwio78WnEwcwqGMznli8g3m/HHR1SUpd0JncAibM3cyP+9J4ZUwPfRRaHaMBXkwDH/vzNa/q2pLnlu7mnTWxej9xVSOdOJPHnR//xq/xx5hxa0+9UVsdpAFeAl8vT94d24cxvYN57bt9vLoyBptNQ1y5RnZ2NpdddhmFhb8/IjDheBY3v/8Lu5Myrd/VEF599VXCwsLo3Lkz3377bYXb27JlCz169CAsLIwpU6ac24F54oknWLNmTaW3RzmPBngpvDw9eP2Wntw1sB0frovn0S+26zM2lUvMnj2bm266CU9PTwB2HTnJTe/9QvqpXOZPHMA13VuzZ88ePv/8c3bv3s2qVat44IEHzgv88rj//vv56KOPiI2NJTY2llWrVgHw0EMPMX26y59frorQAL8ADw/hhRu78dcRnflmexLjPt7Eyax8V5el6pgFCxZw4403AvDKzHkMHDKMegLv3dSBO0cMJCUlhW+++YbbbrsNHx8f2rdvT1hYGJs2bSp1nWvWrGH06NHnhlevXs2YMWNITk4mMzOTgQMHIiKMGzeOr7/+GoB27dpx7NgxUlJSqnJzVTlogJdBRPjL8DDevK0XWw+f4Ob3fyHheJary1J1RF5eHvHx8YSGhvL1tiPMPhJIo2aBXO8VxatPP8q0adNo1aoVR44coU2bNueWCwkJ4ciRI6Wud/jw4cTExJCWZr/uYc6cOUyYMIEjR44QEvL7rWaLr6dPnz78/PPPVbClqiI0wB10Y69gPpkwgKOZOdz03i9EJZ50dUmqFktdkMrG0I0s9VmKzzEfFkzdySOLttMvtCkbl81n5n9ew8fHh9tvv71C6xcR7rrrLubPn09GRgYbN27k2muvLXO5Fi1akJSUVKE2lfNpgJfDoI7N+Or+S/D29OBPH25kbYw+GEI5X+qCVPZO3kvuoVx88CG3IJfm/zzG/aeaM3dCPzLTU/Hw8CA1NRWbzQZAcHAwCQkJ59aRmJhIcHDwBdsZP3488+fPZ+HChdxyyy3Uq1eP4OBgEhN/vwai+HpycnLw8/Nz8haritIAL6dOLf1Z8pdL6BBovx3trPXxepqhcqr4Z+KxZdmD2R9/bNiQgnwuXW7DE8OECRNYuHAhXbp0YcaMGQDccMMNfP755+Tm5nLgwAFiY2Pp378/AFdccUWJ3SlBQUEEBQXx0ksvMX78eABat25No0aN+PXXXzHG8Mknn5zrfwfYt28f3bt3r+q3QDmo1j8Tsyq08Pdl0eRBPP7FDl76XzS7kzJ59aYe+Hp5uro0VQvkHs49bziCCKKIom9CX1555RWGDh3KkCFD6NmzJ/369WPUqFF069aNW2+9la5du1KvXj1mzpyJp6cnNpuN/fv307RpyQ8vHjt2LGlpaXTp0uXcuHfffZd77rmH7Oxsrr322nNdK/n5+ezfv5+IiIiq23hVLlKde48REREmMjKy2tqrajabYeba/by+eh89ggP44K6+BDXWj5eqctYEbcAjueDc8D728SVfMq3dNAYdHFSude3atYvZs2ef21Mv7sEHH6R3795MnDixzHUtWbKErVu38uKLL5arBlV5IrLFGPOH/5zahVIJHh7CQ1d0Yta4CA6kn+H6tzew6cBxV5el3JTNZpixeh8f9j1Nvvfv48MJp7d3b9q92K7c6+zevXup4d23b1927tzJnXfe6dC6CgoKePzxx8tdg6o6ugfuJPuPnmbyJ5EcPp7Fczd0484BbfVucMphx8/k8eii7fy0L41bI0KYkt2ChH8cJPdwLj5tfejwcgdajm3p6jKVi5S2B64B7kSZOfk88vl21sQc5abewbwwujsNffQwg7qwyIPHeWjhNo6dzuPZ67syVv/5q2JKC/BKpYuIHAROAYVAQUkN1CWNfL2YNS6Ct9bE8tYPsWxLyOCdO3rTLSjA1aWpGshmM3y0Pp5/fbuX4MZ+/PeBS+gerL8rynHO6AMfbozpVdfD+ywPD+GRK8P57N6BZOUVMGbmL8z75aCeaqjOk5GVx72fRPLqyhiu7tqS5VOGaHirctODmFVkYIdmrJgylMFhzXhu6W7um79F76OiANhy6Dij3trAutg0nr++K++O7UMjXy9Xl6XcUGUD3ADficgWEZlc0gwiMllEIkUk8ux9F+qKZg19+Pjufkwd1YUfoo8y8q31bD6oZ6nUVbkFhfxzVQy3vL8REVh83yXcM7i99nerCqvUQUwRCTbGHBGRFsBq4CFjzLrS5q/tBzEvZHtCBg8t3EriiWwmDm7PEyM664U/dUh0ciaPLtpOTMop/hTRhqnXdcFf97qVg6rkPHBjzBHr+1FgCdC/MuurzXq1aczKhy/ljv5tmbXhACPfXM+WQydcXZaqYoU2w3s/xnHDOxtIP53HrHER/PP/LtbwVk5R4QAXkQYi4n/2NXA1sMtZhdVGDX3q8fKYHsyfOIDcAhu3vP8Lr66IJidfHxRRGx1MP8OtH2zkn6tiuLJLS7579FKu7KrncivnqcxphC2BJVb/XT3gM2PMKqdUVcsN6dScVY8M5ZUVMXywLp7vo1P59y096dO2iatLU06QW1DIhz/F8/ba/fjU8+CNP/VkdK9g7etWTqcX8rjYun1pPPXVTpIzc7itX1ueHNGZJg28y15Q1Ugb444x9eso4tLOMKpHa/5xXVdaBfi6uizl5vRKzBrsVE4+b34fy5xfDuLvW4+/XXMRf4pog4eH7rG5i2Onc3llRQxfbU2kTVM/XrihO8MvauHqslQtoQHuBvamnOIf3+xi04Hj9GzTmJdu7E6PEL24oyYrtBm+iEzgn6tiOJ1TwORLO/DQ5Z3w89YzjJTzaIC7CWMMX28/wsv/i+HYmVzu6N+WR64MJ9Dfx9WlqSKMMfy4L43pK2LYm3qKfqFNeHlMD8Jb+ru6NFULaYC7mcycfGZ8t49Pfz2ETz0PJg1pz72XdtDTz2qA3UkneXVFDBv2p9OuWX2eHHERI3u00oOUqspogLup+LTTvL56H//bmUyT+l78ZXgYdw1qh089/Yhe3ZIysnntu70s2XaEAD8vplzeiTsHtsO7nt6RQlUtDXA3tzMxg3+t2suG/ekEN/bj0avCGd0riHqeGh5VLfFEFh/8FM+iSPtDg8cPDuWBYWEE+OmnIVU9NMBriQ2x6fxzVQxRR07Spqkfk4d24JaINnpZfhU4kH6Gd9fuZ8m2I4jA//UN4S/DwwhpUt/Vpak6RgO8FrHZDKujU3n/pzi2Hc6gWQNvxg8O5a6BoQTU173CytqbcoqZa/ezfGcSXp4e3N6/LZMv7aDPO1UuowFeCxlj2HTgOO/9FMePe9No4O3JHQPacvclobqXWE4FhTbWxBzl018PsT42nQbentw5qB2ThnTQM4CUy2mA13LRyZl88FMcy3YmYzOGSzsFcnv/tlzRpQVe2k9eqrRTuXwRmcCCXw+RdDKH1gG+3NG/LXcObKdXxKoaQwO8jkjKyGbR5gQWbU4gJTOHQH8fbo0I4bZ+bWnTVPfKwX7xza/xx1i0OYGVu5LJLzQMDmvGXQNDubJLCz0wrGocDfA6pqDQxo9701i46TBr9x7FAAPaN2VUj9aM6N6KFv516/4cxhi2JWSwdHsS/4tKJu1ULv4+9bi5bwh3DmxHWIuGri5RqVJpgNdhSRnZfBGZwLIdScSlnUEE+oc2ZWSP1lzbvRUtGtXOMLfZDHuSM1kRlcyynUkkHM/Gu54Hl3duwQ29grj8ohZ69o5yCxrgCmMM+1JPsyIqmRVRycQePY0I9G7TmCFhzbkkrDm92zZ264uEjp3OZX1sOuv2pbEuNo3003l4egiDw5pzQ88gru7WUp8/qdyOBrj6g9jUU6yISmHt3qPsTMzAZsDPy5N+7ZsyuGMzLunYnM6t/Gv0lYapmTlsT8hge0IGP+9PJ+rISYyBpg28GdqpOZeFB3JZeCDNGuqZJMp9aYCrCzqZnc9v8cf4eX86P8cdY//R0wB4eQqdW/nTPSiAbsEBdA9qRJfWjaq968FmM6SeyiE+7Qw7E0+ywwrtlMwcAOp5CL3aNLYHdudAugcF6O14Va2hAa7KJeVkDpsPHmdX0kl2H8lkV9JJMrLyAfAQaNXIl5Cm9Qlp4kebJvVpY71u1sCbRn5e+PvWw8/L06EbPNlshlM5BRzPyuNEVh4nzuSRfjqXA+lZHEw/w8Fj9q+cfNu5ZUKb1adnm8b0DGlMzzaN6RZU/f9UlKouGuCqUowxJJ3MYdeRk+xJyiTheBaJJ7JJOJFFSmYOJf0aeXoI/r71aOTrhZenYAzYjKHQGGw2+zpzCmxkZOVhK2F5L0+hTdP6tG/WgNDm9q/2zRrQLaiRnqOt6pTSArwyz8RUdYiIENzYj+DGfozo1uq8aXkFNpIyskk8kc2JrDwyc/I5lVPAKet7ZnY++TaDhwgegvXd/tq7ngdN6nvTpIE3Tep7Wd+9adbAm9YBvnpOtlIXoAGuKs27nse5PWSlVPXR3RullHJTGuBKKeWmNMCVUspNaYArpZSb0gBXSik3pQGulFJuSgNcKaXclAa4Ukq5qWq9lF5E0oBDFVy8OZDuxHKcResqH62rfLSu8qmpdUHlamtnjAksPrJaA7wyRCSypHsBuJrWVT5aV/loXeVTU+uCqqlNu1CUUspNaYArpZSbcqcA/9DVBZRC6yofrat8tK7yqal1QRXU5jZ94Eoppc7nTnvgSimlitAAV0opN+WWAS4ij4uIEZHmrq4FQEReFJGdIrJdRL4TkSBX1wQgIv8WkRirtiUi0tjVNQGIyC0isltEbCLi8lO+ROQaEdkrIvtF5ClX1wMgIrNF5KiI7HJ1LUWJSBsRWSsie6yf4cOurglARHxFZJOI7LDqmubqmooSEU8R2SYiy525XrcLcBFpA1wNHHZ1LUX82xhzsTGmF7AceNbF9Zy1GuhujLkY2Af83cX1nLULuAlY5+pCRMQTmAlcC3QFbheRrq6tCoC5wDWuLqIEBcDjxpiuwEDgLzXk/coFLjfG9AR6AdeIyEDXlnSeh4FoZ6/U7QIceAN4EqgxR1+NMZlFBhtQQ2ozxnxnjCmwBn8FQlxZz1nGmGhjzF5X12HpD+w3xsQbY/KAz4EbXVwTxph1wHFX11GcMSbZGLPVen0KeygFu7YqMHanrUEv66tG/B2KSAgwCpjl7HW7VYCLyI3AEWPMDlfXUpyIvCwiCcBYas4eeFETgJWuLqIGCgYSigwnUgMCyR2ISCjQG/jNxaUA57optgNHgdXGmBpRF/Af7DudNmevuMY91FhEvgdalTDpGeBp7N0n1e5CdRljvjHGPAM8IyJ/Bx4EnqsJdVnzPIP9o++C6qjJ0bqU+xKRhsBXwCPFPoG6jDGmEOhlHetZIiLdjTEuPYYgItcBR40xW0RkmLPXX+MC3BhzZUnjRaQH0B7YISJg7w7YKiL9jTEprqqrBAuAFVRTgJdVl4jcA1wHXGGq8aT/crxfrnYEaFNkOMQap0ohIl7Yw3uBMea/rq6nOGNMhoisxX4MwdUHgQcDN4jISMAXaCQi840xdzpj5W7ThWKMiTLGtDDGhBpjQrF/1O1THeFdFhHpVGTwRiDGVbUUJSLXYP/odoMxJsvV9dRQm4FOItJeRLyB24ClLq6pxhL73tPHQLQxZoar6zlLRALPnmUlIn7AVdSAv0NjzN+NMSFWZt0GrHFWeIMbBXgNN11EdonITuxdPDXi1CrgHcAfWG2d4vi+qwsCEJExIpIIDAL+JyLfuqoW6yDvg8C32A/IfWGM2e2qes4SkYXARqCziCSKyERX12QZDNwFXG79Tm239i5drTWw1vob3Iy9D9ypp+zVRHopvVJKuSndA1dKKTelAa6UUm5KA1wppdyUBrhSSrkpDXCllHJTGuBKKeWmNMCVUspN/T9J1/qFF1ycGgAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "x0, x1, x2 = (1, 6), (2, 11), (3, 18)\n",
    "x, y = zip(*[x0, x1, x2])\n",
    "poly = lagrange(x, y)\n",
    "print('---------------')\n",
    "print(poly)\n",
    "print('---------------')\n",
    "val = np.linspace(-4, 4)\n",
    "plt.plot(val, poly(val))\n",
    "\n",
    "plt.plot(x, y, 'om')\n",
    "plt.text(1, 6, '(x0, y0)')\n",
    "plt.text(2, 11, '(x1, y1)')\n",
    "plt.text(3, 18, '(x2, y2)')\n",
    "plt.title('f(x) Lagrangian Interpolation Polynomial')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 访问树的构造\n",
    "以下图所示的访问树为例\n",
    "![access tree](../imgs/access-tree.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 3): None\n",
      "\t(3, 3): None\n",
      "\t\t教师: None\n",
      "\t\t教授: None\n",
      "\t\tX项目: None\n",
      "\t计算机学院: None\n",
      "\t(1, 3): None\n",
      "\t\t人工智能: None\n",
      "\t\t信息安全: None\n",
      "\t\t网络安全: None\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 从叶子结点开始构造\n",
    "t33 = Node.threshold_node(Gate(3, 3), [Node.attr_node('教师'), Node.attr_node('教授'), Node.attr_node('X项目')])\n",
    "t13 = Node.threshold_node(Gate(1, 3), [Node.attr_node('人工智能'), Node.attr_node('信息安全'), Node.attr_node('网络安全')])\n",
    "# root\n",
    "t23 = Node.threshold_node(Gate(2, 3), [t33, Node.attr_node('计算机学院'), t13])\n",
    "print(t23)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 秘密共享\n",
    "假设某个秘密值为10.0，从根节点开始共享，所有非叶子节点的多项式常数均为来自父节点的秘密分片，在递归的过程中，自变量x的值就是孩子节点从左至右的序号，为了方便计算，我们假定所有多项式的非常数项系数均为1，但为了贴合实际，后续代码的实现过程中，我们依然采用随机数的方式来生成所有的系数。\n",
    "![node share](../imgs/node-share.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 3): 10.0\n",
      "\t(3, 3): 96.0\n",
      "\t\t教师: 241.0\n",
      "\t\t教授: 506.0\n",
      "\t\tX项目: 891.0\n",
      "\t计算机学院: 182.0\n",
      "\t(1, 3): 268.0\n",
      "\t\t人工智能: 268.0\n",
      "\t\t信息安全: 268.0\n",
      "\t\t网络安全: 268.0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def secret_share(root: Node, s):\n",
    "    \"\"\" 递归分享秘密值 \"\"\"\n",
    "    root.secret = s\n",
    "    if not root.is_leaf():\n",
    "        coef = np.append(np.random.choice(range(1, 101), size = (1, root.gate.k - 1)), s)\n",
    "        for x, c in enumerate(root.children, 1):\n",
    "            # 计算秘密分片，递归分享\n",
    "            secret_share(c, np.polyval(coef, x))\n",
    "\n",
    "s = 10.0\n",
    "secret_share(t23, s)\n",
    "print(t23)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 秘密恢复\n",
    "在恢复的过程中，从叶子结点开始，自底向上递归恢复，对于叶节点来说，如果它的属性在用户属性列表里面，则视为满足，对于非叶子节点来说，如果叶子结点的满足的个数大于等于k，则视为满足，此时进行拉格朗日插值计算多项式在x = 0处的函数值，并将其赋值给其自身的秘密值，最终，恢复出来的秘密值保存在根节点下。在回复之前，我们首先将所有非叶子节点的秘密值置为None。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def secret_clear(root: Node):\n",
    "    if not root.is_leaf():\n",
    "        root.secret = None\n",
    "        for c in root.children:\n",
    "            secret_clear(c)\n",
    "\n",
    "def secret_recover(root: Node, attrs):\n",
    "    if root.is_leaf():\n",
    "        if root.attr in attrs:\n",
    "            print(f'属性： \\'{root.attr}\\' 满足！')\n",
    "            return True\n",
    "        else:\n",
    "            print(f'属性： \\'{root.attr}\\' 不满足！')\n",
    "            return False\n",
    "    else:\n",
    "        points = []  # 所有满足的子节点集合\n",
    "        for i, c in enumerate(root.children, 1):\n",
    "            if secret_recover(c, attrs):\n",
    "                points.append((i, c.secret))\n",
    "            if len(points) == root.gate.k:\n",
    "                x, y = zip(*points)\n",
    "                # 拉格朗日插值\n",
    "                poly = lagrange(x, y)\n",
    "                root.secret = poly(0)\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "属性： '教师' 满足！\n",
      "属性： '教授' 满足！\n",
      "属性： 'X项目' 满足！\n",
      "属性： '计算机学院' 不满足！\n",
      "属性： '人工智能' 不满足！\n",
      "属性： '信息安全' 满足！\n",
      "秘密恢复成功，秘密值为： 10.0\n"
     ]
    }
   ],
   "source": [
    "attrs = ['教师', '教授', 'X项目', '信息安全'] # recover success\n",
    "# attrs = ['教师', '教授', '信息安全'] # recover failed\n",
    "\n",
    "# clear non-leaf node\n",
    "secret_clear(t23)\n",
    "\n",
    "# secret recover\n",
    "assert secret_recover(t23, attrs), '秘密恢复失败'\n",
    "print('秘密恢复成功，秘密值为：', t23.secret)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.9 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  },
  "vscode": {
   "interpreter": {
    "hash": "d7eccc50bd8023cf74f021c24ed3740245f8543f295cddc81d7590622531cffd"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
